package com.algorithm.example.queue.queue.priority;

import com.algorithm.example.queue.queue.Queue;

import java.util.Iterator;

/**
 * <p>
 * 基于有
 * 序数组实现优先级队列
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/27 16:33
 */
public class PriorityQueue2<E extends Priority> implements Queue<E>, Iterable<E> {

    Priority[] array;
    int size;

    public PriorityQueue2(int capacity) {
        this.array = (E[]) new Priority[capacity + 1];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        insert(value);
        size++;
        return true;
    }

    private void insert(Priority index) {
        int i = size - 1;
        while (i >= 0 && array[i].Priority() > index.Priority()) {
            array[i + 1] = array[i];
            i--;
        }
        array[i + 1] = index;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int i = --size;
        E priority = (E) array[i];
        array[i] = null;
        return priority;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[size-1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = 0;

            @Override
            public boolean hasNext() {
                return p != size;
            }

            @Override
            public E next() {
                Priority priority = array[p];
                p++;
                return (E) priority;
            }
        };
    }
}
